package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/4 15:25
 */
public class J14 {

    /**
     * https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
     */
    public static int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        return process(n, 1);
    }

    private static int process(int restN, int preProduct) {
        if (restN < 1) {
            return restN == 0 ? preProduct : -1;
        }
        int max = 0;
        for (int i = 1; i <= restN; i++) {
            max = Math.max(max, process(restN - i, i * preProduct));
        }
        return max;
    }

    /**
     * 数学推算法
     */
    public static int cuttingRope2(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int a = n / 3, b = n % 3;
        // 余数位0, 返回3的a次方
        if (b == 0) {
            return (int) Math.pow(3, a);
        }
        // 位数为1, 返回3的a-1次方*4
        if (b == 1) {
            return (int) Math.pow(3, a - 1) * 4;
        }
        // 位数为2, 返回3的a次方*2
        return (int) Math.pow(3, a) * 2;
    }

    public static int m (int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1, x = 3;
        for(int a = n / 3 - 1; a > 0; a /= 2) {
            if(a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if(b == 0) return (int)(rem * 3 % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }


    // for test
    public static void main(String[] args) {
        int n = 2;
        for (int i = 1; i <= 20; i++) {
            System.out.println(i + ":" + cuttingRope(i));
        }
    }

}
